//给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。 
//
// 
//
// 示例： 
//
// 输入: "sea", "eat"
//输出: 2
//解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
// 
//
// 
//
// 提示： 
//
// 
// 给定单词的长度不超过500。 
// 给定单词中的字符只含有小写字母。 
// 
// Related Topics 字符串 动态规划 
// 👍 348 👎 0

package com.cute.leetcode.editor.cn;
public class DeleteOperationForTwoStrings {
    public static void main(String[] args) {
        new DeleteOperationForTwoStrings().new Solution().minDistance("leetcode","etco");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 转换成最长公共字符串问题
         * dp[i][j]定义为s1取前0-i个字符和s2取前0-j个字符所能达到的最长公共字符串（两部分任意字符都可取或不取）
         * 那么状态转移方程即为：
         * 如果s1[i] == s2[j] 那么dp[i][j] = dp[i-1][j-1] + 1
         * 如果不等的话，那么可以尝试取s1[i]或尝试取s2[j]
         * 即为 dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]) 即必不取s2[j]可能取s1[i]和必不取s1[i]可能取s2[j]时的最大值
         * 可以增加前导空格便于初始化
         * 最终结果去掉前导空格是最长字符串长度，再两个原始长度分别减去max再相加即可
         *
         * 当然也可以不使用前导空格了
         */
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] dp = new int[len1+1][len2+1];
            /*for (int i = 0; i <= len2 ; i++) {
                dp[0][i] = 1;
            }
            for (int i = 0; i <=len1 ; i++) {
                dp[i][0] = 1;
            }

            char[] c1 = word1.toCharArray();
            char[] c2 = word2.toCharArray();
            for (int i = 1; i <= len1 ; i++) {
                for (int j = 1; j <= len2 ; j++) {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                    if (c1[i-1] == c2[j-1]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
            int max = dp[len1][len2]-1;//去除前导空格
            return len1+len2-2*max;*/

            for (int i = 0; i < len1; i++) {
                for (int j = 0; j < len2; j++) {
                    if (word1.charAt(i) == word2.charAt(j)) dp[i+1][j+1] = dp[i][j]+1;
                    else dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
            return len1+len2-2*dp[len1][len2];
        }


        /**
         *  我的思路是这样的：遍历任意一个字符串，找出并存储按顺序出现的所有字符的位置
         *  然后遍历存储位置的数组，计算差值得到应该删除的个数
         *  这种方法在查询时应该注意两个字符串的查询顺序，
         *  比如"intention"和"execution"在查询时
         *  如果让intention作为s1的话，开始位置的i会使得跳过s2中很长的一部分
         *  还是不行，放弃了
         */
        /*
        public int minDistance(String word1, String word2) {
            return Math.min(helper(word1, word2), helper(word2, word1));
        }


        public int helper(String word1, String word2){
            if (word1.equals(word2)) return 0;
            int res = 0;
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] indexes = new int[Math.max(len1, len2)][2];
            int index = 0;
            int p1 = 0;
            char[] c1 = word1.toCharArray();
            for (int i = 0; i < len1; i++) {
                if (word2.indexOf(c1[i],p1)!=-1){
                    p1 = word2.indexOf(c1[i],p1);
                    indexes[index][0] = i;
                    indexes[index++][1] = p1;
                    p1++;
                }
            }
            if (index==0) return len1+len2;
            for (int i = index-1; i >=1 ; i--) {
                res+= (indexes[i][0]-indexes[i-1][0]-1 + indexes[i][1]-indexes[i-1][1]-1);
            }
            res += (len1 - indexes[index - 1][0] - 1 + len2 - indexes[index - 1][1] - 1 + indexes[0][0] + indexes[0][1]);
            return res;
        }*/

        /**
         * 二刷的时候想到的是一刷题解中的方法，看完代码随想录的题解之后发现可以直接存储最小删除步数
         */
        public int minDistance2(String word1, String word2) {
            char[] chars1 = word1.toCharArray();
            char[] chars2 = word2.toCharArray();
            int[][] dp = new int[chars1.length+1][chars2.length+1];
            //初始化，转换为空串只能全删
            for (int i = 1; i <= chars1.length ; i++) dp[i][0] = i;
            for (int i = 1; i <= chars2.length ; i++) dp[0][i] = i;
            for (int i = 1; i <= chars1.length; i++) {
                for (int j = 1; j <= chars2.length; j++) {
                    // 如果当前字符相等的话，就直接取上一个匹配的值加一
                    if (chars1[i-1] == chars2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                    // 如果当前字符不等的话，就可以删一个或者删两个，一共三种情况，去最小值就行了
                    else dp[i][j] = Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+2);
                }
            }
            return dp[chars1.length][chars2.length];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}